/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/combination-sum
   @Language: C++
   @Datetime: 16-02-09 05:45
   */

class Solution {
	void getsum(vector<int> &can,int tar,int pos
			,vector<vector<int> > &vs, vector<int> &v){
		if (tar==0){
			vs.push_back(v);
			return;
		}
		for(int i=pos; i<can.size() && can[i]<=tar; ++i){
			// skip duplicate set
			if (i!=pos && can[i]==can[i-1]) continue;
			v.push_back(can[i]);
			getsum(can,tar-can[i],i,vs,v);
			v.pop_back();
		}
	}
public:
	/**
	 * @param candidates: A list of integers
	 * @param target:An integer
	 * @return: A list of lists of integers
	 * Tip: all elements can be used multiply,
	 *      but the result sets must have unique set
	 */
	vector<vector<int> > combinationSum(vector<int> &can, int tar) {
		// write your code here
		vector<vector<int> > vs;
		vector<int> v;
		sort(can.begin(),can.end());
		getsum(can,tar,0,vs,v);
		return vs;
	}
};
